/*
 * Copyright (c) 2011 Seoul National University
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Jung Ho Ahn  ( gajh@snu.ac.kr )
 *
 */

#ifndef __KMER_H__
#define __KMER_H__

#include <iostream>
#include <cassert>
#include <cstdint>
using namespace std;

typedef uint64_t KmerUnit;
typedef uint64_t HashUnit;
const int nNtPerUnit               = (8 * sizeof(KmerUnit)) / 2;
const uint64_t nBitKmerUnitMinusNt = 8 * sizeof(KmerUnit) - 2;

enum nucleotide_type { nt_A=0x00, nt_C=0x01, nt_G=0x02, nt_T=0x03, nt_I = 0x04};


class ContigNode;


// gajh assumes that length is an odd number
#if defined __MAX_KMER_SIZE_31__

class Kmer
{
  public:
    Kmer() : kmer(0) { assert(lenR <= 31); }
    Kmer(const Kmer & k) : kmer(k.kmer) { }
    ~Kmer() { }
    Kmer & operator=(const Kmer & k);
    
    void pushFromLSB(nucleotide_type n);  // previously push()
    void pushFromMSB(nucleotide_type n);  // previously pushLeft()
    HashUnit getHashValue() const { return kmer ^ (kmer >> 32); }
    bool operator==(const Kmer & dst) const { return (dst.kmer == kmer); }
    bool operator<(const Kmer & dst)  const { return (dst.kmer > kmer); }
    inline int32_t getLength() { return lenR; }
    inline KmerUnit   getLSW() const { return kmer ^ (kmer >> 32); }
    nucleotide_type getLSBNucleotide() { return (nucleotide_type)(0x3 & kmer); }
    nucleotide_type getMSBNucleotide() { return (nucleotide_type)(0x3 & (kmer >> ((lenR - 1) << 1))); }
    void setLSBNucleotide(nucleotide_type n) { kmer = (kmer & (KmerUnit)(~0x3)) | n; }
    void setMSBNucleotide(nucleotide_type n) { kmer = (kmer & (~((KmerUnit)0x3 << ((lenR - 1) << 1)))) | (((KmerUnit)n) << ((lenR - 1) << 1)); }
    void reverseComplement();

    static nucleotide_type charToNucleotide(char n);
    static nucleotide_type charToComplementaryNucleotide(char n);
    static inline nucleotide_type ComplementaryNucleotide(nucleotide_type n) { return (nucleotide_type)(3 - (int)n); }
    static bool            isValidNucleotide(char n);
    static char            nucleotideToChar(nucleotide_type n);
    static const KmerUnit filter = ((KmerUnit)0x3) << nBitKmerUnitMinusNt;

  private:
    static int32_t lenQ;  // quotient of length
    static int32_t lenR;  // remainder of length
    KmerUnit kmer;

    nucleotide_type popLSB();

  friend class KmerCoverageTable;
  friend ostream & operator<<(ostream & out, const Kmer & k);
  friend ostream & operator<<(ostream & out, const ContigNode & k);
};

#elif defined __MAX_KMER_SIZE_63__

class Kmer
{
  public:
    Kmer() : kmerL(0), kmerH(0) { assert(lenR + lenQ*nNtPerUnit <= 63 && lenR + lenQ*nNtPerUnit > 32); }
    Kmer(const Kmer & k) : kmerL(k.kmerL), kmerH(k.kmerH) { }
    ~Kmer() { }
    Kmer & operator=(const Kmer & k);
    
    void pushFromLSB(nucleotide_type n);  // previously push()
    void pushFromMSB(nucleotide_type n);  // previously pushLeft()
    HashUnit getHashValue() const { return kmerL ^ kmerH; }
    bool operator==(const Kmer & dst) const { return (dst.kmerL == kmerL && dst.kmerH == kmerH); }
    bool operator<(const Kmer & dst) const  { return (dst.kmerH == kmerH ? dst.kmerL > kmerL : dst.kmerH > kmerH); }
    inline int32_t  getLength() { return lenR + lenQ*nNtPerUnit; }
    inline KmerUnit getLSW() const { return kmerL ^ kmerH; }
    nucleotide_type getLSBNucleotide() { return (nucleotide_type)(0x3 & kmerL); }
    nucleotide_type getMSBNucleotide() { return (nucleotide_type)(0x3 & (kmerH >> ((lenR - 1) << 1))); }
    void setLSBNucleotide(nucleotide_type n) { kmerL = (kmerL & (KmerUnit)(~0x3)) | n; }
    void setMSBNucleotide(nucleotide_type n) { kmerH = (kmerH & (~((KmerUnit)0x3 << ((lenR - 1) << 1)))) | (((KmerUnit)n) << ((lenR - 1) << 1)); }
    void reverseComplement();

    static nucleotide_type charToNucleotide(char n);
    static nucleotide_type charToComplementaryNucleotide(char n);
    static inline nucleotide_type ComplementaryNucleotide(nucleotide_type n) { return (nucleotide_type)(3 - (int)n); }
    static bool            isValidNucleotide(char n);
    static char            nucleotideToChar(nucleotide_type n);
    static const KmerUnit filter = ((KmerUnit)0x3) << nBitKmerUnitMinusNt;

  private:
    static int32_t lenQ;  // quotient of length
    static int32_t lenR;  // remainder of length
    KmerUnit kmerL, kmerH;

    nucleotide_type popLSB();

  friend class KmerCoverageTable;
  friend ostream & operator<<(ostream & out, const Kmer & k);
  friend ostream & operator<<(ostream & out, const ContigNode & k);
};

#elif defined __MAX_KMER_SIZE_95__

class Kmer
{
  public:
    Kmer() : kmerL(0), kmerM(0), kmerH(0) { assert(lenR + lenQ*nNtPerUnit <= 95 && lenR + lenQ*nNtPerUnit > 64); }
    Kmer(const Kmer & k) : kmerL(k.kmerL), kmerM(k.kmerM), kmerH(k.kmerH) { }
    ~Kmer() { }
    Kmer & operator=(const Kmer & k);
    
    void pushFromLSB(nucleotide_type n);  // previously push()
    void pushFromMSB(nucleotide_type n);  // previously pushLeft()
    HashUnit getHashValue() const { return kmerL ^ kmerM; }
    bool operator==(const Kmer & dst) const { return (dst.kmerL == kmerL && dst.kmerM == kmerM && dst.kmerH == kmerH); }
    bool operator<(const Kmer & dst) const  { return (dst.kmerH == kmerH ? ((dst.kmerM == kmerM) ? dst.kmerL > kmerL : dst.kmerM > kmerM) : dst.kmerH > kmerH); }
    inline int32_t  getLength() { return lenR + lenQ*nNtPerUnit; }
    inline KmerUnit getLSW() const { return kmerL ^ kmerM; }
    nucleotide_type getLSBNucleotide() { return (nucleotide_type)(0x3 & kmerL); }
    nucleotide_type getMSBNucleotide() { return (nucleotide_type)(0x3 & (kmerH >> ((lenR - 1) << 1))); }
    void setLSBNucleotide(nucleotide_type n) { kmerL = (kmerL & (KmerUnit)(~0x3)) | n; }
    void setMSBNucleotide(nucleotide_type n) { kmerH = (kmerH & (~((KmerUnit)0x3 << ((lenR - 1) << 1)))) | (((KmerUnit)n) << ((lenR - 1) << 1)); }
    void reverseComplement();

    static nucleotide_type charToNucleotide(char n);
    static nucleotide_type charToComplementaryNucleotide(char n);
    static inline nucleotide_type ComplementaryNucleotide(nucleotide_type n) { return (nucleotide_type)(3 - (int)n); }
    static bool            isValidNucleotide(char n);
    static char            nucleotideToChar(nucleotide_type n);
    static const KmerUnit filter = ((KmerUnit)0x3) << nBitKmerUnitMinusNt;

  private:
    static int32_t lenQ;  // quotient of length
    static int32_t lenR;  // remainder of length
    KmerUnit kmerL, kmerM, kmerH;

    nucleotide_type popLSB();

  friend class KmerCoverageTable;
  friend ostream & operator<<(ostream & out, const Kmer & k);
  friend ostream & operator<<(ostream & out, const ContigNode & k);
};

#else
#define __GENERAL_KMER__

class Kmer
{
  public:
    Kmer(); // zero-argument default constructor is required by google-sparse-hash
    Kmer(const Kmer & k);
    ~Kmer();
    Kmer & operator=(const Kmer & k);
    
    void pushFromLSB(nucleotide_type n);  // previously push()
    void pushFromMSB(nucleotide_type n);  // previously pushLeft()
    inline HashUnit getHashValue() const { return kmer[0] ^ (kmer[0] >> 32); }
    bool operator==(const Kmer & dst) const;
    bool operator<(const Kmer & dst) const;
    inline int32_t  getLength() { return lenR + lenQ*nNtPerUnit; }
    inline KmerUnit getLSW() const { return kmer[0] ^ (kmer[0] >> 32); }
    nucleotide_type getLSBNucleotide() { return (nucleotide_type)(0x3 & kmer[0]); }
    nucleotide_type getMSBNucleotide() { return (nucleotide_type)(0x3 & (kmer[lenQ] >> ((lenR - 1) << 1))); }
    void setLSBNucleotide(nucleotide_type n) { kmer[0] = (kmer[0] & (KmerUnit)(~0x3)) | n; }
    void setMSBNucleotide(nucleotide_type n) { kmer[lenQ] = (kmer[lenQ] & (~((KmerUnit)0x3 << ((lenR - 1) << 1)))) | (((KmerUnit)n) << ((lenR - 1) << 1)); }
    void reverseComplement();

    static nucleotide_type charToNucleotide(char n);
    static nucleotide_type charToComplementaryNucleotide(char n);
    static inline nucleotide_type ComplementaryNucleotide(nucleotide_type n) { return (nucleotide_type)(3 - (int)n); }
    static bool            isValidNucleotide(char n);
    static char            nucleotideToChar(nucleotide_type n);
    static const KmerUnit filter = ((KmerUnit)0x3) << nBitKmerUnitMinusNt;

  private:
    static int32_t lenQ;  // quotient of length
    static int32_t lenR;  // remainder of length
    KmerUnit *kmer;

    nucleotide_type popLSB();

  friend class KmerCoverageTable;
  friend ostream & operator<<(ostream & out, const Kmer & k);
  friend ostream & operator<<(ostream & out, const ContigNode & k);
};

#endif



struct KmerHashConfiguration
{
  HashUnit operator()(const Kmer * key_value) const
  {
    return key_value->getHashValue();
  }

  HashUnit operator()(const Kmer & key_value) const
  {
    return key_value.getHashValue();
  }
};


struct KmerEqual
{
  bool operator()(const Kmer * left, const Kmer * right) const
  {
    return *left == *right;
  }
  bool operator()(const Kmer & left, const Kmer & right) const
  {
    return left == right;
  }
};


struct KmerLt
{
  bool operator()(const Kmer * left, const Kmer * right) const
  {
    return *left < *right;
  }

  bool operator()(const Kmer & left, const Kmer & right) const
  {
    return left < right;
  }
};

#endif
